package org.chnxi.study.leetcode.questions25.ques20;

import java.util.Stack;

/**
 * 有效的括号 - 使用栈进行记录
 * 执行用时 :2 ms, 在所有 Java 提交中击败了82.25%的用户
 * 内存消耗 :37.5 MB, 在所有 Java 提交中击败了5.48%的用户
 */
public class Simple01 {

    public static void main(String[] args) {
        String str0 = " ";
        System.out.println("result="+isValid(str0));

        String str1 = "()";
        System.out.println("result="+isValid(str1));

        String str2 = "()[]{}";
        System.out.println("result="+isValid(str2));

        String str3 = "(]";
        System.out.println("result="+isValid(str3));

        String str4 = "([)]";
        System.out.println("result="+isValid(str4));

        String str5 = "{[]}";
        System.out.println("result="+isValid(str5));

        String str6 = "){";
        System.out.println("result="+isValid(str6));
    }

    public static boolean isValid(String s) {
        if(s == null || s.length() < 1){
            return true;
        }
        //声明一个栈，存储未找到匹配的括号，如果最终栈为空，表示均匹配到
        Stack<Character> stack = new Stack<>();

        char[] chars = s.toCharArray();

        //遍历字符串
        for(int i=0; i<chars.length; i++){
            char curChar = chars[i];
            //从栈中取出头节点，判断与当前节点是否匹配为一对括号
            Character head = stack.isEmpty() ? null : stack.peek();

            //如果匹配成功，将这一对括号丢弃
            if(head != null && (
                    (head == '(' && curChar == ')')
                      || (head == '[' && curChar == ']')
                      || (head == '{' && curChar == '}')
                    )
            ){
                stack.pop();
            }else{
                //匹配不成功，将当前括号压住占用，用于后续匹配
                stack.push(curChar);
            }
        }

        //如果都匹配成功，栈为空
        return stack.isEmpty();
    }

}
